## The Meggitt decoder. Presupposes a precomputed Meggitt table E

from PyM import *

def meggitt_decoder(y,g):
    x = variable(g)
    s = remainder(y,g)
    if s==0: return y
    j = 0
    while lookup(s,E)==0:
        j += 1; s = remainder(x*s,g)
    e = lookup(s,E)/x**j
    return y-e


def lookup(k,T):
    for (a,b) in T:
        if a==k: return b
    return 0

[_,x] = polynomial_ring(Zn(3),'x')

g = x**5+x**4-x**3+x**2-1

# Example relative to the ternary Golay code. Table precomputed (meggit_table_golay3)


E=[(x**4 + x**3 + 2*x**2 + x, x**10), (2*x**4 + 2*x**3 + x**2 + 2*x, 2*x**10), (x**4
+ x**3 + 2*x**2 + x + 1, x**10 + 1), (x**4 + x**3 + 2*x**2 + x + 2, x**10 + 2
), (2*x**4 + 2*x**3 + x**2 + 2*x + 1, 2*x**10 + 1), (2*x**4 + 2*x**3 + x**2 + 2*
x + 2, 2*x**10 + 2), (x**4 + x**3 + 2*x**2 + 2*x, x**10 + x), (x**4 + x**3 + 2*x
**2, x**10 + 2*x), (2*x**4 + 2*x**3 + x**2, 2*x**10 + x), (2*x**4 + 2*x**3 + x**
2 + x, 2*x**10 + 2*x), (x**4 + x**3 + x, x**10 + x**2), (x**4 + x**3 + x**2 + x,
 x**10 + 2*x**2), (2*x**4 + 2*x**3 + 2*x**2 + 2*x, 2*x**10 + x**2), (2*x**4 + 2*
x**3 + 2*x, 2*x**10 + 2*x**2), (x**4 + 2*x**3 + 2*x**2 + x, x**10 + x**3), (x**4
 + 2*x**2 + x, x**10 + 2*x**3), (2*x**4 + x**2 + 2*x, 2*x**10 + x**3), (2*x**4 +
 x**3 + x**2 + 2*x, 2*x**10 + 2*x**3), (2*x**4 + x**3 + 2*x**2 + x, x**10 + x**4
), (x**3 + 2*x**2 + x, x**10 + 2*x**4), (2*x**3 + x**2 + 2*x, 2*x**10 + x**4), (
x**4 + 2*x**3 + x**2 + 2*x, 2*x**10 + 2*x**4), (2*x**3 + x**2 + x + 1, x**10 + x
**5), (2*x**4 + x + 2, x**10 + 2*x**5), (x**4 + 2*x + 1, 2*x**10 + x**5), (x**3 
+ 2*x**2 + 2*x + 2, 2*x**10 + 2*x**5), (2*x**3 + 2*x + 2, x**10 + x**6), (2*x**4
 + x**2 + 1, x**10 + 2*x**6), (x**4 + 2*x**2 + 2, 2*x**10 + x**6), (x**3 + x + 1
, 2*x**10 + 2*x**6), (x**3 + x**2 + 2, x**10 + x**7), (2*x**4 + x**3 + 2*x + 1, 
x**10 + 2*x**7), (x**4 + 2*x**3 + x + 2, 2*x**10 + x**7), (2*x**3 + 2*x**2 + 1, 
2*x**10 + 2*x**7), (2*x**4 + 2*x**3 + 2*x**2 + 2, x**10 + x**8), (2*x**2 + 2*x +
 1, x**10 + 2*x**8), (x**2 + x + 2, 2*x**10 + x**8), (x**4 + x**3 + x**2 + 1, 
2*x**10 + 2*x**8), (x**4 + 2*x**3 + 1, x**10 + x**9), (x**4 + x**2 + 2*x + 2, 
x**10 + 2*x**9), (2*x**4 + 2*x**2 + x + 1, 2*x**10 + x**9), (2*x**4 + x**3 + 2, 2*x**10
+ 2*x**9)]

y = x**4+x**3+x+1

z=meggitt_decoder(y,g)

show(z)